package JavaStudy.Search;

import java.util.Scanner;

//插值查找，一般用于数据量较大，关键字分布较均匀的时候，若分布不均匀，可以用折半插值
//和二分查找不同的是插值查找每次从自适应 mid 处开始查找。
public class insertValueSearch {
    public static int Search(int[] arr,int left,int right,int findVal){
        if(left>right||findVal<arr[left]||findVal>arr[right]){
            return -1;
        }
        // 求出mid, 自适应
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal) { // 说明应该向右边递归
            return Search(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 说明向左递归查找
            return Search(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
    public static void main(String[] args) {
        //一般来说要先将数组排序，但是我这里主要学的是查找不是排序，故写一个顺序数组，省去排序（要排序二分查找那里有
        int[] a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
        System.out.println("请输入你要查找的数字（数组内容为：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}");
        Scanner input=new Scanner(System.in);
        int num=input.nextInt();
        int left=0;
        int right=a.length-1;
        int result=Search(a,left,right,num);
        if (result==-1){
            System.out.println("没有哦");
        }else {
            System.out.println("找到了，在第"+(result+1)+"个");
        }
    }
}
